#include <bits/stdc++.h>

using namespace std;

// 找到所有好字符串
// 给你两个长度为n的字符串s1和s2，以及一个字符串evil
// 好字符串的定义为 : 长度为n，字典序大于等于s1，字典序小于等于s2，且不包含evil字符串
// 返回好字符串的数量
// 由于答案很大返回对1000000007取余的结果
// 测试链接 : https://leetcode.cn/problems/find-all-good-strings/

class Solution 
{
public:
    static const int MOD = 1000000007;
    static const int MAXN = 501;
    static const int MAXM = 51;
    int dp[MAXN][MAXM][2];
    int next[MAXM];
    
    void clear(int n, int m)
    {
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                dp[i][j][0] = -1;
                dp[i][j][1] = -1;
            }
        }
    }

    void nextArray(string& s, int m)
    {
        next[0] = -1;
        next[1] = 0;
        int i = 2, cn = 0;
        while(i < m)
        {
            if(s[i - 1] == s[cn])
                next[i++] = ++cn;
            else if(cn > 0)
                cn = next[cn];
            else
                next[i++] = 0;
        }
    }

    int kmp(string& s1, string& s2, int n, int m)
    {
        int x = 0, y = 0;
        while(x < n && y < m)
        {
            if(s1[x] == s2[y])
                ++x, ++y;
            else if(y == 0)
                ++x;
            else
                y = next[y];
        }
        return y == m ? x - y : -1;
    }

	// 时间复杂度O(n * m * 2 * 26)
	// s、e、n、m都是固定参数
	// 0...i-1已经做了决策，已经匹配了e[0...j-1]这个部分
	// 当前来到s[i]时，最先该考察的匹配位置是e[j]
	// 之前的决策如果已经比s小了，free == 1
	// 之前的决策如果和s[0..i-1]一样，free == 0
	// 返回后续的所有决策中，不含有e字符串且<=s的决策有多少个，同时长度需要为n
	// 核心 : 利用e字符串的next数组加速匹配
    int f(string& s, string& e, int n, int m, int i, int j, int free)
    {
        if(j == m)
        {
			// 一旦配出了e的整体
			// 说明之前的决策已经违规
			// 后续有效决策数量0
            return 0;
        }
		// 能跑如下代码
		// 之前的决策不含有整个e字符串
        if(i == n)
        {
			// 说明所有决策已经做完了
			// 并且不含有e字符串
			// 同时决策的每一步都保证了不会比s大
			// 返回1种有效决策(之前做的所有决定)
            return 1;
        }
        if(dp[i][j][free] != -1) return dp[i][j][free];
        int ans = 0;
        char cur = s[i];
        if(free == 0)
        {
			// 之前的决策和s的状况一样
			// 当前尝试比cur小的字符
            for(char pick = 'a'; pick < cur; ++pick)
            {
                ans = (ans + f(s, e, n, m, i + 1, jump(pick, e, j) + 1, 1)) % MOD;
            }
            // 当前尝试等于cur的字符
            ans = (ans + f(s, e, n, m, i + 1, jump(cur, e, j) + 1, 0)) % MOD;
        }
        else
        {
			// 之前的决策已经确定小于s了
			// 当前a~z随便尝试
            for(char pick = 'a'; pick <= 'z'; ++pick)
            {
                ans = (ans + f(s, e, n, m, i + 1, jump(pick, e, j) + 1, 1)) % MOD;
            }
        }
		dp[i][j][free] = ans;
		return ans;
    }

	// 当前字符是pick，一开始匹配e[j]
	// 根据next数组加速匹配，返回匹配出来的位置
	// 如果匹配不出来返回-1
	// 单次调用的时间复杂度O(1)
    int jump(char pick, string& e, int j)
    {
        while(j >= 0 && pick != e[j])
        {
            j = next[j];
        }
        return j;
    }

    int findGoodStrings(int n, string s1, string s2, string evil) 
    {
        int m = evil.size();
        nextArray(evil, m);
        clear(n, m);
        // <=s2的好字符串数量
        int ans = f(s2, evil, n, m, 0, 0, 0);
        clear(n, m);
        // 减去<=s1的好字符串数量
        ans = (ans - f(s1, evil, n, m, 0, 0, 0) + MOD) % MOD;
        if(kmp(s1, evil, n, m) == -1) ans = (ans + 1) % MOD;
        return ans;
    }
};


class Solution 
{
public:
    static const int MOD = 1000000007;
    static const int MAXM = 51;
    int next[MAXM];

    void nextArray(string& s, int m)
    {
        next[0] = -1;
        next[1] = 0;
        int i = 2, cn = 0;
        while(i < m)
        {
            if(s[i - 1] == s[cn])
                next[i++] = ++cn;
            else if(cn > 0)
                cn = next[cn];
            else
                next[i++] = 0;
        }
    }

    int kmp(string& s1, string& s2, int n, int m)
    {
        int x = 0, y = 0;
        while(x < n && y < m)
        {
            if(s1[x] == s2[y])
                ++x, ++y;
            else if(y == 0)
                ++x;
            else
                y = next[y];
        }
        return y == m ? x - y : -1;
    }

    int f(string& s, string& e)
    {
        int n = s.size(), m = e.size();
        int dp[n][m];
        memset(dp, -1, sizeof dp);
        function<int(int, int, bool)> dfs = [&](int i, int j, bool is_limit) -> int
        {
            if(j == m) return 0;
            if(i == n) return 1;
            if(!is_limit && dp[i][j] != -1) return dp[i][j];
            int ans = 0;
            char up = is_limit ? s[i] : 'z'; // i 位置所填字母的上限
            for(char d = 'a'; d <= up; ++d)
            {
                int ej = j;
                // i 位置上的 d 字符去匹配字符 e[ej]
                // i + 1 位置的字符去匹配 ej + 1 位置上的字符
                while(ej != -1 && d != e[ej]) ej = next[ej];
                ans = (ans + dfs(i + 1, ej + 1, is_limit && d == up)) % MOD; 
            }
            if(!is_limit) dp[i][j] = ans;
            return ans;
        };
        return dfs(0, 0, true);
    }

    int findGoodStrings(int n, string s1, string s2, string evil) 
    {
        int m = evil.size();
        nextArray(evil, m);
        int ans = (f(s2, evil) - f(s1, evil) + MOD) % MOD;
        if(kmp(s1, evil, n, m) == -1) ans = (ans + 1) % MOD;
        return ans;
    }
};